答疑
题目 答疑
思路分析
模拟了一下案例 顺序是132得到的2.8s
贪心吗 1 3 2的顺序是3s 8s 9s 总时间排序？
有个前缀和的思路在里面
原本发信息的时间只和自己的进入和答疑时间有关 但是后面的人 要累加上前面已经做过的人的进入和答疑时间以及离开时间 也就是总时间
所以分为两部分
一是固有的（必须要用的时间）——所有人的进入和答疑时间之和
二是因为顺序不同 需要等待的时间 如果某人排在第一位 就需要把它的总时间*总人数 所有人都要等这段时间
贪心也在这里得到证明 高权值配低消耗 总结果最小
代码实现
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long LL;
const int N=1010;
int si[N],ai[N],ei[N];
LL sumi[N];
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n;cin>>n;
LL must=0; //必须时间
for(int i=0;i<n;i++){
cin>>si[i]>>ai[i]>>ei[i];
sumi[i]=si[i]+ai[i]+ei[i];
must+=si[i]+ai[i]; // 累加进入和答疑时间到 d，离开时间不计入
}
sort(sumi,sumi+n);
LL sum=must;//总时间为 固有时间加等待时间
int t=n;
for(int i=0;i<n-1;i++){//等待时间与顺序有关 看后面有多少人
sum+=(t-1)*sumi[i];
t--;
}
cout<<sum;
return 0;
}
💬 评论